package com.atguigu.recursion;

public class MiGongDemo {
    public static void main(String[] args) {
        MiGongMap miGongMap = new MiGongMap();
        miGongMap.constructOuterWall();

        miGongMap.printMap();

        goMap(miGongMap,new MovePoint(1,1));

        miGongMap.printMap();

    }

    /**
     * 走迷宫
     * 通过此方法的个人感悟.
     * 对于比较复杂的递归问题, 通常会有一条或若干条可成功或失败的分支, 递归的目的就是找到其中一条成功的分支.
     * 核心代码分为3个模块:
     * 1. 成功结束点. 不再需要(向下)递归, 同时会传递成功的最初信号.
     * 2. 失败结束点. 不再需要(向下)递归, 同时会传递失败的最初信号.
     * 3. 中继点.
     * 3.1. 需要(向下)递归(才能感知下游信号) -- 最直观的体现
     * 3.2. 同时将成功或失败信号传给父栈(除非是最外部调用) -- 逆向思考/回环作用 (梳理逻辑时, 从此环节出发比较容易)
     * 3.3. 通常会有多个,否则说明问题可能比较简单(至少实际应该走多个分支)
     * 3.4. 由于递归最后要得到一个成功结果即可, 故在向下递归调用时, 优先处理成功情况(成功则直接将信息传递给父栈), 失败则转而考虑其他的中继点.
     *
     * 递归所传递的信息, 包含两部分:
     * 1. 分支路线是否成功
     * 2. 副作用数据. 在本例中, 就是实际行走路线
     *
     * @param miGongMap m
     * @param movePoint m
     * @return b
     */
    public static boolean goMap(MiGongMap miGongMap,MovePoint movePoint){
        if (miGongMap.isFinish()) {
            // 走到这里, 表示是成功的真正结束
            return true;
        }else if(miGongMap.movePointType(movePoint)==MiGongMap.TYPE_EMPTY){
            // 只要能进入这里, 表示此前节点到目前为止,均可以走(但还不能最终确定这条路线就一定是可行的)

            // 先假定可以走(通过此信息,传递成功的路线信号)
            miGongMap.changePointType(movePoint,MiGongMap.TYPE_GOING);
            // 策略:下->右->上->左
            if (goMap(miGongMap,movePoint.goDown())) {
                // 走到这里,表示这条路线没有问题, 该节点是成功的. 需要将成功的信号上传给上一个节点
                return true;
            }else if(goMap(miGongMap,movePoint.goRight())){
                return true;
            }else if(goMap(miGongMap,movePoint.getUp())){
                return true;
            }else if(goMap(miGongMap,movePoint.goLeft())){
                return true;
            }else{
                // 如果走到这里,表示上下邹游皆不可走通,即该路线是不可行的
                // 与上面相对,走到这里, 表示这条路线有问题, 同时将失败的信号上传给上一个节点(消除上一个节点的分支)
                // 由于此前假定了该路线成功,所以这里需要再改信号标识这个路线失败
                miGongMap.changePointType(movePoint,MiGongMap.TYPE_NOT_WORK);
                return false;
            }
        }else{
            // 直接表示当前点不可走
            return false;
        }
    }
}


class MovePoint{
    private final int row;
    private final int col;

    public MovePoint(int row, int col) {
        this.row = row;
        this.col = col;
    }

    public int getRow() {
        return row;
    }

    public int getCol() {
        return col;
    }

    public MovePoint goLeft(){
        return new MovePoint(row,col-1);
    }

    public MovePoint goRight(){
        return new MovePoint(row,col+1);
    }

    public MovePoint getUp(){
        return new MovePoint(row-1,col);
    }

    public MovePoint goDown(){
        return new MovePoint(row+1,col);
    }

    public boolean equals(MovePoint movePoint){
        return movePoint.getRow()==row&&movePoint.getCol()==col;
    }


}

class MiGongMap{

    private static int DEFAULT_COL_COUNT=7;
    private static int DEFAULT_ROW_COUNT=8;

    // 没有走过的位置
    public static int TYPE_EMPTY=0;
    // 墙,不可走
    public static int TYPE_WALL=1;
    // 走过的位置
    public static int TYPE_GOING=2;
    // 已确定不可走的位置
    public static int TYPE_NOT_WORK =3;

    private int rowCount;
    private int colCount;

    private int[][] map;

    public MiGongMap() {
        this.rowCount=DEFAULT_ROW_COUNT;
        this.colCount=DEFAULT_COL_COUNT;
        this.map=new int[rowCount][colCount];
        constructOuterWall();
        constructInnerWall();
    }

    public MiGongMap(int rowCount,int colCount) {
        this.rowCount = rowCount;
        this.colCount = colCount;
        this.map=new int[rowCount][colCount];
        constructOuterWall();
        constructInnerWall();
    }

    /**
     * 构建外墙
     */
    public void constructOuterWall(){
        for (int i = 0; i < this.colCount; i++) {
            map[0][i]=TYPE_WALL;
            map[rowCount-1][i]=TYPE_WALL;
        }
        for (int i = 0; i < this.rowCount; i++) {
            map[i][0]=TYPE_WALL;
            map[i][colCount-1]=TYPE_WALL;
        }
    }

    /**
     * 构建内部障碍
     */
    public void constructInnerWall(){
        // todo 修改此处, 改变内墙结构
        map[3][1]=1;
        map[3][2]=1;
        map[2][2]=1;
    }


    public int getColCount() {
        return colCount;
    }

    public int getRowCount() {
        return rowCount;
    }

    public int[][] getMap() {
        return map;
    }

    public MovePoint endPoint(){
        return new MovePoint(rowCount-2,colCount-2);
    }

    public int movePointType(MovePoint movePoint){
        return map[movePoint.getRow()][movePoint.getCol()];
    }

    public boolean isFinish(){
        return movePointType(endPoint())==MiGongMap.TYPE_GOING;
    }

    public void changePointType(MovePoint movePoint,int type){
        map[movePoint.getRow()][movePoint.getCol()]=type;
    }

    public void printMap(){
        System.out.println("print map:");
        for (int[] ints : map) {
            for (int anInt : ints) {
                System.out.print(anInt + " ");
            }
            System.out.println();
        }
    }

}
